package com.ryujung.number.leetCode_1137;

/*
The Tribonacci sequence Tn is defined as follows: 

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

*/
public class Solution {
    /**
     * 斐波那契数列，从第四个数开始，tn为前三个数的和 
     * t0=0,t1=1,t2=1
     * 思路：递归
     * n>3,从t3计算到tn，使用三个变量，用于计算下一个数的值，
     * 每次计算出一个值，就用第四个变量记录这个值，
     * 然后三个变量重新指向自己前一个数，第三个变量指向刚刚记录的变量四
     * n=3则记录一次，4--两次，5--三次
     * for(int i=3;i>=n; i++){计算值并重新指向}
     */
    public static int tribonacci(int n) {
        if (n < 2) {//0和1对应的值就是n本身
            return n;
        }

        int t0 = 0, t1 = 1, t2 = 1,t3=0;
        if (n == 2) {//n为2时值为1
            return 1;
        }

        for (int i = 3; i <= n; i++) {//n>3就需要从n=3进行推算，并记录最近推算的三个值，用于推算下一个值
            t3 = t0 + t1 + t2; //推算下一个值
            t0 = t1;  //将三个变量重新指向新的值
            t1 = t2;
            t2 = t3;
        }

        return t3;
    }

    /**
     * 
    Example 1:
    Input: n = 4
    Output: 4
    Explanation:
    T_3 = 0 + 1 + 1 = 2
    T_4 = 1 + 1 + 2 = 4

    Example 2:
    Input: n = 25
    Output: 1389537
     */
    public static void main(String[] args) {
        int i = 25;
        System.out.println(tribonacci(i));
    }
}